Digital image composing and manipulation is used to provide special effects in movies and in a variety of graphics applications. In the movies, image composition and digital manipulation techniques have been used to realistically combine objects or regions from various still frames or photographs into new frames to create a seamless, convincing image or image sequence.
One aspect of digital image composing involves digital segmentation. During segmentation, an object within an image is traced so that it may be extracted from the image. Segmentation was originally performed manually, with a user selecting points along the boundary edges of an image to outline the image. The more points entered, the more accurate the outline. However, the time required to place points at each image was time consuming, often resulting in a rough approximation and consequently providing a poor resultant output image.
Computer-based segmentation tools have been provided to attempt to automate portions of the tracing process. However, the tools frequently offer little advantage over manual tracing. A selection of digital image segmentation tools includes region-based `magic wands`, active contours or snakes, or a graph searching formulation of digital processing to find globally optimal boundaries.
In region based `magic wands` segmentation, a seed point is selected on the edge of an image by a user. The selected seed point is used to grow a region by adding adjacent neighboring pixels to help define edges to provide a higher granularity edge detection. Region growing does not, however, provide interactive visual feedback. As a result, region boundaries must usually reedited or modified manually.
Active contour or snake segmentation is used to improve a manually entered rough approximation. Once the rough boundary approximation is provided, boundary points are adjusted in parallel with the boundary. An energy function is computed based on a combination of internal forces relating to curve energy and external forces related to image gradient magnitude. Active contouring is used to minimize the energy function to approximate the boundary. Unfortunately, the user does not know what the final boundary is until the energy minimization step is completed. If the resulting boundary is not satisfactory, the boundary must be manually edited, and the process must be repeated until a satisfactory boundary is selected. Thus the active contour or snake method is an iterative process that still requires frequent manual intervention.
In graph searching dynamic programming, a manually entered boundary template is provided, and remaining boundary points are computer generated in a stage-wise optimal cost function. Thus, in contrast to the snake, active contour method, there is no iterative energy approximation performed. However, because there is no manual intervention besides the initial supply of the boundary template, the benefits of human guidance and expertise are lost.
An intelligent scissors computer tool described in Intelligent Scissors for Image Composition, Computer Graphics Proceedings, Annual Conference Series, 1995, has been provided for balancing the benefits of manual intervention with the advantages provided by computer generated boundary points. An example of tracing using the intelligent scissors tracing tool is illustrated in FIG. 1 with image 10. During intelligent scissors segmentation, a seed point 14 is placed on a boundary edge of a selected object 12 in the image, and a path data structure is generated from the seed point. When a gestured mouse position places a point such as point 16 close to the edge of an object, a live-wire boundary snaps to the boundary of object 12 by snapping to the lowest cost nearby pixel. Thus a line, also referred to as a `live wire` 18 is generated and wraps the object 12 by following paths in the path data structure back to the seed point 14. Thus, boundary edges are mathematically determined using dynamic programming based on minimal energy comparison techniques.
A problem arises in intelligent scissors segmentation when a pixel at a boundary of a desired object has a higher gradient magnitude than a pixel at a boundary of a nearby object. In the intelligent scissors approach, a gradient magnitude of each pixel is initially determined. The gradient magnitude is a measure of change of color of that pixel from a neighboring pixel. Thus, it can be inferred that a higher gradient magnitude indicates an edge. Higher gradient magnitude pixels are assigned lower costs. If two objects are adjacent in an image, such as object 12 and object 20 in image 10, a boundary pixel of object 20 will have a lower cost than a boundary pixel of object 12. Thus, if a pixel is selected on the boundary of object 12, the lower cost of a pixel on the boundary of object 20 may result in the pixel being snapped to a boundary edge of object 20. Thus, a live wire segment such as segment 22 will be erroneously provided.
To correct the problem of incorrect boundary snapping the intelligent scissors approach of the prior art uses dynamic training techniques. During dynamic training, characteristics about a last generated live-wire segment are stored. When a next boundary point is selected, the boundary edge having the most similar characteristics with the previous live-wire segment is selected.
One drawback of dynamic training is that, since it is based on the edge characteristics from the last live-wire boundary, it is less effective for those objects with inconsistent or changing edge characteristics. In fact, training can be counter productive for objects with sudden and dramatic changes in edge features. As such, training is often turned on and off, depending upon the edge characteristics of an object.